πŸ‘©β€πŸ’» 2146. 닀리 λ§Œλ“€κΈ°

@Seongukbaek Posted February 10, 2022 Β· Updated February 10, 2022 Β· 9 min read

문제

μ—¬λŸ¬ μ„¬μœΌλ‘œ 이루어진 λ‚˜λΌκ°€ μžˆλ‹€. 이 λ‚˜λΌμ˜ λŒ€ν†΅λ Ήμ€ 섬을 μž‡λŠ” 닀리λ₯Ό λ§Œλ“€κ² λ‹€λŠ” κ³΅μ•½μœΌλ‘œ 인기λͺ°μ΄λ₯Ό ν•΄ 당선될 수 μžˆμ—ˆλ‹€. ν•˜μ§€λ§Œ 막상 λŒ€ν†΅λ Ήμ— μ·¨μž„ν•˜μž, 닀리λ₯Ό λ†“λŠ”λ‹€λŠ” 것이 μ•„κΉλ‹€λŠ” 생각을 ν•˜κ²Œ λ˜μ—ˆλ‹€. κ·Έλž˜μ„œ κ·ΈλŠ”, μƒμƒ‰λ‚΄λŠ” μ‹μœΌλ‘œ ν•œ 섬과 λ‹€λ₯Έ 섬을 μž‡λŠ” 닀리 ν•˜λ‚˜λ§Œμ„ λ§Œλ“€κΈ°λ‘œ ν•˜μ˜€κ³ , κ·Έ λ˜ν•œ 닀리λ₯Ό κ°€μž₯ 짧게 ν•˜μ—¬ λˆμ„ 아끼렀 ν•˜μ˜€λ‹€.

이 λ‚˜λΌλŠ” NΓ—N크기의 이차원 평면상에 μ‘΄μž¬ν•œλ‹€. 이 λ‚˜λΌλŠ” μ—¬λŸ¬ μ„¬μœΌλ‘œ 이루어져 있으며, μ„¬μ΄λž€ λ™μ„œλ‚¨λΆμœΌλ‘œ μœ‘μ§€κ°€ λΆ™μ–΄μžˆλŠ” 덩어리λ₯Ό λ§ν•œλ‹€.

κ·Έλ¦Όμ—μ„œ 색이 μžˆλŠ” 뢀뢄이 μœ‘μ§€μ΄κ³ , 색이 μ—†λŠ” 뢀뢄이 바닀이닀. 이 바닀에 κ°€μž₯ 짧은 닀리λ₯Ό 놓아 두 λŒ€λ₯™μ„ μ—°κ²°ν•˜κ³ μž ν•œλ‹€. κ°€μž₯ 짧은 λ‹€λ¦¬λž€, 닀리가 κ²©μžμ—μ„œ μ°¨μ§€ν•˜λŠ” 칸의 μˆ˜κ°€ κ°€μž₯ μž‘μ€ 닀리λ₯Ό λ§ν•œλ‹€. λ‹€μŒ κ·Έλ¦Όμ—μ„œ 두 λŒ€λ₯™μ„ μ—°κ²°ν•˜λŠ” 닀리λ₯Ό λ³Ό 수 μžˆλ‹€.

λ¬Όλ‘  μœ„μ˜ 방법 외에도 닀리λ₯Ό λ†“λŠ” 방법이 μ—¬λŸ¬ κ°€μ§€ μžˆμœΌλ‚˜, μœ„μ˜ κ²½μš°κ°€ λ†“λŠ” λ‹€λ¦¬μ˜ 길이가 3으둜 κ°€μž₯ μ§§λ‹€(λ¬Όλ‘  길이가 3인 λ‹€λ₯Έ 닀리λ₯Ό 놓을 수 μžˆλŠ” 방법도 λͺ‡ κ°€μ§€ μžˆλ‹€). 지도가 μ£Όμ–΄μ§ˆ λ•Œ, κ°€μž₯ 짧은 닀리 ν•˜λ‚˜λ₯Ό 놓아 두 λŒ€λ₯™μ„ μ—°κ²°ν•˜λŠ” 방법을 μ°ΎμœΌμ‹œμ˜€.

μž…λ ₯

  • 첫 μ€„μ—λŠ” μ§€λ„μ˜ 크기 N(100μ΄ν•˜μ˜ μžμ—°μˆ˜)κ°€ μ£Όμ–΄μ§„λ‹€. κ·Έ λ‹€μŒ Nμ€„μ—λŠ” N개의 μˆ«μžκ°€ λΉˆμΉΈμ„ 사이에 두고 μ£Όμ–΄μ§€λ©°, 0은 λ°”λ‹€, 1은 μœ‘μ§€λ₯Ό λ‚˜νƒ€λ‚Έλ‹€. 항상 두 개 μ΄μƒμ˜ 섬이 μžˆλŠ” λ°μ΄ν„°λ§Œ μž…λ ₯으둜 μ£Όμ–΄μ§„λ‹€.

좜λ ₯

  • 첫째 쀄에 κ°€μž₯ 짧은 λ‹€λ¦¬μ˜ 길이λ₯Ό 좜λ ₯ν•œλ‹€.

πŸ“ Logic

class Loc { int x; int y; int cnt; public Loc(int x, int y, int cnt) { this.x = x; this.y = y; this.cnt = cnt; } public int getX() { return x; } public int getY() { return y; } public int getCnt() { return cnt; } }
  • 각 정점별 μ’Œν‘œ 및 ν˜„μž¬ μ •μ κΉŒμ§€ μ˜€λŠ”λ° ν•„μš”ν•œ 닀리 수λ₯Ό μ €μž₯ν•˜κΈ° μœ„ν•΄ μ‚¬μš©ν•˜λŠ” 클래슀
class Graph { final int[][] graph; boolean[][] discovered; Queue<Loc> q = new LinkedList<>(); int[] w_way = { 1, 0, -1, 0 }; int[] y_way = { 0, 1, 0, -1 }; int bridge = Integer.MAX_VALUE; int graph_size; ... }
  • κ·Έλž˜ν”„μ˜ 정보λ₯Ό μ €μž₯ν•˜κΈ° μœ„ν•΄ μ‚¬μš©ν•˜λŠ” 클래슀
private int buildBridge(int x, int y) { discovered = new boolean[graph_size][graph_size]; q = new LinkedList<>(); q.add(new Loc(x, y, 0)); int cur_land = graph[x][y]; discovered[x][y] = true; while(!q.isEmpty()) { Loc loc = q.poll(); int cur_x = loc.getX(); int cur_y = loc.getY(); int cnt = loc.getCnt(); if (graph[cur_x][cur_y] != 0 && graph[cur_x][cur_y] != cur_land) return cnt; for (int i = 0; i < 4; i++) { int nextX = cur_x + w_way[i], nextY = cur_y + y_way[i]; if (nextX < 0 || nextX >= graph_size || nextY < 0 || nextY >= graph_size) continue; if (discovered[nextX][nextY] || graph[nextX][nextY] == cur_land) continue; discovered[nextX][nextY] = true; q.add(new Loc(nextX, nextY, cnt+1)); } } return -1; }
  • κ΅¬λΆ„λœ λŒ€λ₯™ 정보λ₯Ό κ°€μ§€κ³ , μ„œλ‘œ λ‹€λ₯Έ λŒ€λ₯™μ„ μž‡λŠ” 닀리λ₯Ό λ†“μ•„λ³΄λŠ” λ©”μ†Œλ“œ
  • if (graph[cur_x][cur_y] != 0 && graph[cur_x][cur_y] != cur_land) return cnt; 을 톡해 μ„œλ‘œ λ‹€λ₯Έ λŒ€λ₯™μ„ 이은 경우 μ‚¬μš©λœ 닀리 길이 + 1 이 λ°˜ν™˜
  • λ°©λ¬Έν•˜μ§€ μ•Šμ€ 0 , 즉 λ°”λ‹€μ˜ κ²½μš°μ—λ§Œ 계속 Queue 에 μΆ”κ°€

πŸ“„ CODE

μ½”λ“œ 보기/μ ‘κΈ°πŸ’«
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; class Loc { int x; int y; int cnt; public Loc(int x, int y, int cnt) { this.x = x; this.y = y; this.cnt = cnt; } public int getX() { return x; } public int getY() { return y; } public int getCnt() { return cnt; } } class Graph { final int[][] graph; boolean[][] discovered; Queue<Loc> q = new LinkedList<>(); int[] w_way = { 1, 0, -1, 0 }; int[] y_way = { 0, 1, 0, -1 }; int bridge = Integer.MAX_VALUE; int graph_size; public Graph(int size) { graph_size = size; this.graph = new int[graph_size][graph_size]; discovered = new boolean[graph_size][graph_size]; } public void AddElement(String line, int idx) { String[] tmp = line.split(" "); for(int i = 0; i < graph_size; i++) { graph[idx][i] = Integer.parseInt(tmp[i]); } } public void identifyLand() { int land = 2; for (int i = 0; i < graph_size; i++) { for (int j = 0; j < graph_size; j++) { if (!discovered[i][j] && graph[i][j] == 1) { fillLand(i, j, land); land++; } } } } private void fillLand(int x, int y, int land) { graph[x][y] = land; discovered[x][y] = true; q.add(new Loc(x, y, 0)); while(!q.isEmpty()) { Loc loc = q.poll(); int nowX = loc.getX(); int nowY = loc.getY(); for (int i = 0; i < 4; i++) { int nextX = nowX + w_way[i], nextY = nowY + y_way[i]; if (nextX < 0 || nextX >= graph_size || nextY < 0 || nextY >= graph_size) continue; if (discovered[nextX][nextY]) continue; if (graph[nextX][nextY] == 1) { graph[nextX][nextY] = land; discovered[nextX][nextY] = true; q.add(new Loc(nextX, nextY, 0)); } } } } public void solution() { for (int i = 0; i < graph_size; i++) { for (int j = 0; j < graph_size; j++) { if (graph[i][j] > 0) { int cnt = buildBridge(i, j); if (cnt == -1) continue; bridge = Math.min(bridge, cnt); } } } System.out.println(bridge - 1); } private int buildBridge(int x, int y) { discovered = new boolean[graph_size][graph_size]; q = new LinkedList<>(); q.add(new Loc(x, y, 0)); int cur_land = graph[x][y]; discovered[x][y] = true; while(!q.isEmpty()) { Loc loc = q.poll(); int cur_x = loc.getX(); int cur_y = loc.getY(); int cnt = loc.getCnt(); if (graph[cur_x][cur_y] != 0 && graph[cur_x][cur_y] != cur_land) return cnt; for (int i = 0; i < 4; i++) { int nextX = cur_x + w_way[i], nextY = cur_y + y_way[i]; if (nextX < 0 || nextX >= graph_size || nextY < 0 || nextY >= graph_size) continue; if (discovered[nextX][nextY] || graph[nextX][nextY] == cur_land) continue; discovered[nextX][nextY] = true; q.add(new Loc(nextX, nextY, cnt+1)); } } return -1; } } public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); Graph g = new Graph(N); String line=""; for (int idx = 0; idx < N; idx++) { line = br.readLine(); g.AddElement(line, idx); } g.identifyLand(); g.solution(); br.close(); } }

✏️ Review

  • Queue 에 데이터 μΆ”κ°€, μ‚­μ œ, 검색 μ‹œ μ‚¬μš©ν•˜λŠ” λ©”μ†Œλ“œλ“€ 쀑 μœ μ‚¬ν•œ κΈ°λŠ₯을 ν•˜λŠ” λ©”μ†Œλ“œλ“€μ˜ 차이λ₯Ό μ•„λž˜ μ°Έκ³  λΈ”λ‘œκ·Έμ—μ„œ 확인할 수 μžˆμ—ˆλ‹€.
  • 섬을 κ΅¬λΆ„ν•˜μ—¬ μ €μž₯ν•˜κ³ , 이후 닀리λ₯Ό 건섀할 λ•Œ μ„¬μ˜ κ°€μž₯μžλ¦¬λΆ€ν„° 탐색을 μ‹œμž‘ν•˜λ©΄ μ–΄λ–¨κΉŒλΌλŠ” 생각을 ν–ˆλ‹€.

    • μ„¬μ˜ κ°€μž₯자리λ₯Ό ꡬ뢄해 μ €μž₯해놓고 νƒμƒ‰ν•˜λ €λ‹ˆ, μ„¬μ˜ κ°€μž₯자리λ₯Ό κ΅¬λΆ„ν•˜λŠ” 것이 λ¬Έμ œμ˜€λ‹€.
  • μ„¬μ˜ κ°€μž₯자리λ₯Ό κ΅¬λΆ„ν•˜μ§€ μ•Šκ³ , 브루트 포슀 처럼 λͺ¨λ“  μ„¬μ˜ μ’Œν‘œμ—μ„œ νƒμƒ‰ν•˜λŠ” λ°©μ‹μœΌλ‘œ λ³€κ²½ν–ˆκ³ , λ©”λͺ¨λ¦¬ μ΄ˆκ³Όκ°€ λ°œμƒν–ˆλ‹€.
graph[nowX][nowY] = land; discovered[nowX][nowY] = true; for (int i = 0; i < 4; i++) { int nextX = nowX + w_way[i], nextY = nowY + y_way[i]; if (nextX >= 0 && nextX < graph_size && nextY >= 0 && nextY < graph_size && graph[nextX][nextY] == 1 && !discovered[nextX][nextY]) { q.add(new Loc(nextX, nextY, 0)); } } // μœ„ μ½”λ“œλ₯Ό μ•„λž˜μ™€ 같이 λ³€κ²½, λ©”λͺ¨λ¦¬ μ΄ˆκ³Όκ°€ λ°œμƒν•˜μ§€ μ•ŠμŒ if (nextX < 0 || nextX >= graph_size || nextY < 0 || nextY >= graph_size) continue; if (discovered[nextX][nextY]) continue; if (graph[nextX][nextY] == 1) { graph[nextX][nextY] = land; discovered[nextX][nextY] = true; q.add(new Loc(nextX, nextY, 0)); }
  • λΈ”λ‘œκ·Έλ₯Ό μ°Έκ³ ν•˜μ—¬ μœ„μ˜ μ½”λ“œ μˆ˜μ •μœΌλ‘œ λ©”λͺ¨λ¦¬μ΄ˆκ³Όλ₯Ό ν”Όν•  수 μžˆμ—ˆλŠ”λ°, λ…Όλ¦¬μ μœΌλ‘œ 이해가 κ°€μ§€ μ•ŠλŠ”λ‹€...

πŸ“• 좜처

https://www.acmicpc.net/problem/2146

μ°Έκ³ 

@Seongukbaek
배우고 μ •λ¦¬ν•˜κ³  κ³΅μœ ν•˜λŠ” λŒ€ν•™μƒ λ°±μ„±μš±μž…λ‹ˆλ‹€ πŸ˜€